/**
 * 二叉树的链式定义和前中后序遍历
 */

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10  //环形队列长度

typedef struct BNode{
    int data;
    struct BNode* LChild;   //左孩子
    struct BNode* RChild;   //右孩子
}BNode, *BTree;

//二叉树先序遍历
void preOrder(BTree &bTree);

//二叉树中序遍历
void inOrder(BTree &bTree);

//二叉树后序遍历
void postOrder(BTree &bTree);

int main()
{
    BTree bTree=(BNode* )malloc(sizeof(BNode));
    bTree->data=1;
    bTree->LChild=(BNode*)malloc(sizeof(BNode));
    bTree->LChild->data=2;
    bTree->RChild=(BNode*)malloc(sizeof(BNode));
    bTree->RChild->data=3;
    bTree->RChild->LChild=NULL;
    bTree->RChild->LChild=NULL;
    bTree->LChild->LChild=(BNode*)malloc(sizeof(BNode));
    bTree->LChild->LChild->data=4;
    bTree->LChild->RChild=NULL;
    bTree->LChild->LChild->LChild=NULL;
    bTree->LChild->LChild->RChild=NULL;

    printf("前序遍历结果为:\t");
    preOrder(bTree);
    printf("\n");
    printf("中序遍历结果为:\t");
    inOrder(bTree);
    printf("\n");
    printf("后序遍历结果为:\t");
    postOrder(bTree);
    printf("\n");
    return 0;
}

void preOrder(BTree &bTree)
{
    if(bTree)
    {
        printf("%d ",bTree->data);  //访问当前根节点的值
        preOrder(bTree->LChild);        //寻找左孩子
        preOrder(bTree->RChild);        //寻找右孩子
    }
}

void inOrder(BTree &bTree)
{
    if(bTree)
    {
        inOrder(bTree->LChild);
        printf("%d ",bTree->data);
        inOrder(bTree->RChild);
    }
}

void postOrder(BTree &bTree)
{
    if(bTree)
    {
        postOrder(bTree->LChild);
        postOrder(bTree->RChild);
        printf("%d ",bTree->data);
    }
}